package com.data.basic.chapter06;

/** 二分搜索树的测试代码
 *
 * 递归【自己的理解】：
 *      1.找到终止条件，通常是递归规模最小的一部操作；
 *      2.执行递归    规模量传递  和  操作数
 * Created by wangbing on 2018/5/6.
 */
public class BST<E extends Comparable<E>> {
    /**
     * 添加元素{不包括重复的元素，如果要包括重复元素的话，那么定义：左子树小于等于节点，或者右子树大于等于节点}
     *
     * @param e
     */
    public void add(E e){
        Node newNode=new Node(e);
        if (root==null){
            root=newNode;
            size++;
        }
        else{
            add(root,e);

        }
    }
/**
 * 向以node为根的二分搜索树中插入元素E，递归算法
 *
 * 1.递归终止的条件
 *
 */

    private void add(Node node, E e) {
//        1.递归终止的条件
        if (e.equals(node.e)){
            return;
        }else if (e.compareTo(node.e)<0&&node.left==null){
            node.left = new Node(e);
            size++;
            return;

        }else if(e.compareTo(node.e)>0&&node.right==null){
            node.right =new Node(e);
            size++;
            return;
        }
//      执行递归
        if (e.compareTo(node.e)<0){
            add(node.left,e);
        }else{
            add(node.right,e);
        }

    }


    private class Node{
        /**
         * 二分搜索树的节点类
         */
        public E e;
        public Node left,right;

        public Node(E e) {
            this.e = e;
            this.left = null;
            this.right = null;
        }
    }

    private Node root;
    private int size;

    public BST() {
        root = null;
        size=0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty(){
        return size==0;
    }
}
